/*
 * @Author: Morales
 * @Date: 2020-11-17 19:04:27
 * @LastEditTime: 2020-11-17 20:16:15
 * @E-mail: lovexposed@foxmail.com
 * @Powered by: Havoc_Wei
 */
#include<bits/stdc++.h>
using namespace std;
typedef struct {
    int weight; // 结点的权值
    int parent, lc, rc; // 结点的双亲、左孩子、右孩子的下标
}HTNode, *HuffmanTree;

//* 选择权值最小的两棵树
void SelectMin(HuffmanTree hT, int n, int &s1, int &s2)
{
    s1 = 0;
    s2 = 0;
    int i;
    for(i=1; i<n; ++i)
        if(!hT[i].parent)
        {
            if(!s1) s1 = i;
            else
            {
                s2 = i;
                break;
            }
        }
    if(hT[s1].weight > hT[s2].weight)
        swap(s1, s2);
    for(i+=1; i<n; ++i)
        if(!hT[i].parent)
        {
            if(hT[i].weight <hT[s1].weight)
            {
                s2 = s1;
                s1 = i;
            }
            else if(hT[i].weight <hT[s2].weight)
                s2 = i;
        }
}

//* 构造有n个权值（叶子节点）的哈夫曼树
void CreateHuffmanTree(HuffmanTree &ht)
{
    int n, m;
    cin>>n;
    m = n*2-1;
    ht = new HTNode[m+1]; //* 0号结点不使用
    for(int i=1; i<=m; i++)
        ht[i].parent = ht[i].lc = ht[i].rc = 0;
    for(int i=1; i<=n; i++)
        cin>>ht[i].weight;
    ht[0].weight = m; // 0号结点保存结点数量
    /*----初始化完毕，创建哈夫曼树----*/
    for(int i=n+1; i<=m; i++)
    { // 通过n-1次的选择、删除、合并来创建哈夫曼树
        int s1, s2;
        SelectMin(ht, i, s1, s2);
        ht[s1].parent = ht[s2].parent = i;
        ht[i].lc = s1;
        ht[i].rc = s2;
        ht[i].weight = ht[s1].weight+ht[s2].weight;
    }
}

//* 计算WPL
int HuffmanTreeWPL_(HuffmanTree ht, int i, int depth)
{
    if(!ht[i].lc && !ht[i].rc) return ht[i].weight*depth;
    else return HuffmanTreeWPL_(ht, ht[i].lc, depth+1)+HuffmanTreeWPL_(ht, ht[i].rc, depth+1);
}
int HuffmanTreeWPL(HuffmanTree ht)
{
    return HuffmanTreeWPL_(ht, ht[0].weight, 0);
}

//* 输出哈夫曼树各结点的状态
void Print(HuffmanTree ht)
{
    cout<<"index weight parent lChild rChild"<<endl;
    cout<<left;
    for(int i=1; i<=ht[0].weight; i++)
    {
        cout<<setw(5)<<i<<" ";
        cout<<setw(6)<<ht[i].weight<<" ";
        cout<<setw(6)<<ht[i].parent<<" ";
        cout<<setw(6)<<ht[i].lc<<" ";
        cout<<setw(6)<<ht[i].rc<<endl;
    }
}

//* 销毁哈夫曼树
void DestoyHuffmanTree(HuffmanTree &ht)
{
    delete[] ht;
    ht = NULL;
}

int main()
{
    HuffmanTree ht;
    CreateHuffmanTree(ht);
    Print(ht);
    cout<<"WPL = "<<HuffmanTreeWPL(ht)<<endl;
    DestoyHuffmanTree(ht);
    return 0;
}